import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: XMQ
 * Date: 2022-05-20
 * Time: 8:22
 */
//LeetCode刷题调试代码
public class Test {

    public static void getNext(String sub,int[] next){
        //next数组，前两项默认
        next[0] = -1;
        next[1] = 0;


        //下标i从2开始
        int i = 2;
        int k = 0;//前一项的k值

        //用for循环能对的原因是java实例化数组时默认给数组里都赋值了0
        while(i < sub.length()){
            //求i位置的k值
            if(k == -1 || sub.charAt(i-1) == sub.charAt(k)){
                next[i] = k+1;
                i++;
                k++;
            }else{
                //不相等时，k就一直往后退,直到相等或k等于-1
                k = next[k];
            }
        }
    }
    public static int KMP(String str,String sub,int pos){
        int lenStr = str.length();
        int lenSub = sub.length();

        int i =pos;//主串下标
        int j = 0;//子串下标

        if(str == null || sub ==null) return -1;
        if(lenStr == 0 || lenSub == 0) return -1;
        if(pos < 0 || pos >= lenStr)    return -1;
        if(str.charAt(i) == sub.charAt(j) && lenStr == 1) return 0;

        //获取next数组
        int[] next = new int[lenSub];
        getNext(sub,next);

        while(i < lenStr && j < lenSub){
            //j = -1 就是从 0下标开始
            if(j == -1 || str.charAt(i)  == sub.charAt(j)){
                i++;
                j++;
            }else{
                //i不动，j回到next数组j下标里的k值位置
                j = next[j];
            }
        }
        if(j >= lenSub){
            return i-j;
        }
        return -1;
    }
    public static int strStr(String haystack, String needle) {
        int i = 0;//主串下标
        int j = 0;//子串下标

        int lenStr = haystack.length();
        int lenSub = needle.length();

        if(haystack == null || needle == null) return -1;
        if(lenStr == 0 || lenSub == 0) return -1;

        while(i < lenStr && j < lenSub){
            if(haystack.charAt(i) == needle.charAt(j)){
                i++;
                j++;
            }else{
                i = i-j+1;
                j = 0;
            }
        }
        if(j >= lenSub){
            return i-j;
        }
        return -1;
    }
    public static boolean isAnagram(String s, String t) {
        //创建两个数组，对应所有小写字母下标
        int[] s1 = new int[26];
        int[] t1 = new int[26];

        int count1 = 0;
        int count2 = 0;
        //遍历两个字符串，标记到数组里
        for(int i = 0; i < s.length();i++){
            count1 = s.charAt(i) - 97;
            s1[count1]++;
        }
        for(int i = 0; i < t.length();i++){
            count2 = t.charAt(i) - 97;
            t1[count2]++;
        }
        //如果两个数组所有的值都相同，则返回true
        int count3 = 0;
        for(int i = 0; i < s1.length;i++){
            if(s1[i] == t1[i]){
                count3++;
            }
        }
        if(count3 == 26){
            return true;
        }
        return false;
    }
    public static boolean isPalindrome(int x) {
        if( x < 0) return false;
        if( x < 10) return true;

        String s = "" + x;

        int i = 0;//i从头遍历
        int j = s.length()-1;//j从尾遍历
        while(i <= j){
            if(s.charAt(i) == s.charAt(j)){
                i++;
                j--;
            }else{
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isPalindrome(11));
    }
    public static void main3(String[] args) {
        System.out.println(isAnagram("anagram","nagaram"));
        int i = 10;
//        String s = String.valueOf(i);
        String s1 = "" + i;
        System.out.println(s1);
    }
    public static void main2(String[] args) {
        System.out.println(strStr("ababcabcdads", "abcd"));
        System.out.println(strStr("ababcabcdads", "abcdf"));
        System.out.println(strStr("ababcabcdads", "ab"));
    }
    public static void main1(String[] args) {
        //KMP
        System.out.println(KMP("ababcabcdads", "abcd", 0));
        System.out.println(KMP("ababcabcdads", "abcdf", 0));
        System.out.println(KMP("bba", "a", 0));
    }
}
